'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-09-11 08:50:10
'''
'''
216. 组合总和 III
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。
解集不能包含重复的组合。 
示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]


tips:利用二进制的性质，可以只遍历含有k个数都组合。其原则是找到最低位都连续1，然后将这些连续1都最高位进一位，其余低位都转移
到最低位去，这样就是大小刚好大于这个二进制数，且保证1都个数不变都下个二进制数。如
0100011011->0100011101, 010011100->010100011, 0110->1010。照此规则操作可以将二进制数从满足1都个数都最小值，遍历到最大值。

在这个题中，就是总共九位都二进制数，选取出来k个1的，然后这k个1代表都数加起来还为n。
'''
from typing import List
class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        ans = []
        tmp = [i for i in range(1, k+1)]
        tmp.append(10)
        while True:
            if sum(tmp[:-1]) == n:
                ans.append(tmp[:-1])
            i=0
            while i<k and tmp[i+1] == tmp[i]+1:
                i+=1
            if i == k:
                break
            tmp[i]+=1
            for ii in range(i):
                tmp[ii] = ii+1

        return ans
if __name__ == "__main__":
    solution = Solution()
    k = 3
    n = 9
    print(solution.combinationSum3(k, n))